{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recommender Systems 2020/21\n",
    "\n",
    "### Practice 4 - Cython for SLIM MSE\n",
    "\n",
    "\n",
    "### Cython is a superset of Python, allowing you to use C-like operations and import C code. Cython files (.pyx) are compiled and support static typing.\n",
    "\n",
    "### Why do we use it (or any other compiled language)? If the code is written properly it is fast... I mean, FAST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's implement something simple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPrime(n):\n",
    "    \n",
    "    i = 2\n",
    "    \n",
    "    # Usually you loop up to sqrt(n)\n",
    "    while i < n:\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "        \n",
    "        i += 1\n",
    "        \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is prime 2? True\n",
      "Is prime 3? True\n",
      "Is prime 5? True\n",
      "Is prime 15? False\n",
      "Is prime 20? False\n"
     ]
    }
   ],
   "source": [
    "print(\"Is prime 2? {}\".format(isPrime(2)))\n",
    "print(\"Is prime 3? {}\".format(isPrime(3)))\n",
    "print(\"Is prime 5? {}\".format(isPrime(5)))\n",
    "print(\"Is prime 15? {}\".format(isPrime(15)))\n",
    "print(\"Is prime 20? {}\".format(isPrime(20)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is Prime 80000023? True, time required 9.58 sec\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "result = isPrime(80000023)\n",
    "\n",
    "print(\"Is Prime 80000023? {}, time required {:.2f} sec\".format(result, time.time()-start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Load Cython magic command, this takes care of the compilation step. If you are writing code outside Jupyter you'll have to compile using other tools. See at the end of the notebook for details."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext Cython"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Declare Cython function, paste the same code as before. The function will be compiled and then executed with a Python interface"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "def isPrime(n):\n",
    "    \n",
    "    i = 2\n",
    "    \n",
    "    # Usually you loop up to sqrt(n)\n",
    "    while i < n:\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "        \n",
    "        i += 1\n",
    "        \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is Prime 80000023? True, time required 4.48 sec\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "result = isPrime(80000023)\n",
    "\n",
    "print(\"Is Prime 80000023? {}, time required {:.2f} sec\".format(result, time.time()-start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### As you can see by just compiling the same code we got some improvement.\n",
    "#### To go seriously higher, we have to use some static tiping"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "# Declare the tipe of the arguments\n",
    "def isPrime(long n):\n",
    "    \n",
    "    # Declare index of for loop\n",
    "    cdef long i\n",
    "    \n",
    "    i = 2\n",
    "    \n",
    "    # Usually you loop up to sqrt(n)\n",
    "    while i < n:\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "        \n",
    "        i += 1\n",
    "        \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is Prime 80000023? True, time required 0.22 sec\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "result = isPrime(80000023)\n",
    "\n",
    "print(\"Is Prime 80000023? {}, time required {:.2f} sec\".format(result, time.time()-start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Cython code with two tipe declaration, for n and i, runs 50x faster than Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Main benefits of Cython:\n",
    "* Compiled, no interpreter\n",
    "* Static typing, no overhead\n",
    "* Fast loops, no need to vectorize. Vectorization sometimes performes lots of useless operations\n",
    "* Numpy, which is fast in python, when opertions are not vectorizable often becomes slooooow compared to a carefully written Cython code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SLIM MSE with Cython\n",
    "\n",
    "#### Load the usual data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Movielens10M: Verifying data consistency...\n",
      "Movielens10M: Verifying data consistency... Passed!\n",
      "DataReader: current dataset is: <class 'Data_manager.Dataset.Dataset'>\n",
      "\tNumber of items: 10681\n",
      "\tNumber of users: 69878\n",
      "\tNumber of interactions in URM_all: 10000054\n",
      "\tValue range in URM_all: 0.50-5.00\n",
      "\tInteraction density: 1.34E-02\n",
      "\tInteractions per user:\n",
      "\t\t Min: 2.00E+01\n",
      "\t\t Avg: 1.43E+02\n",
      "\t\t Max: 7.36E+03\n",
      "\tInteractions per item:\n",
      "\t\t Min: 0.00E+00\n",
      "\t\t Avg: 9.36E+02\n",
      "\t\t Max: 3.49E+04\n",
      "\tGini Index: 0.57\n",
      "\n",
      "\tICM name: ICM_genres, Value range: 1.00 / 1.00, Num features: 20, feature occurrences: 21564, density 1.01E-01\n",
      "\tICM name: ICM_tags, Value range: 1.00 / 69.00, Num features: 10217, feature occurrences: 108563, density 9.95E-04\n",
      "\tICM name: ICM_all, Value range: 1.00 / 69.00, Num features: 10237, feature occurrences: 130127, density 1.19E-03\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from Notebooks_utils.data_splitter import train_test_holdout\n",
    "from Data_manager.Movielens.Movielens10MReader import Movielens10MReader\n",
    "\n",
    "data_reader = Movielens10MReader()\n",
    "data_loaded = data_reader.load_data()\n",
    "\n",
    "URM_all = data_loaded.get_URM_all()\n",
    "\n",
    "URM_train, URM_test = train_test_holdout(URM_all, train_perc = 0.8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<69878x10681 sparse matrix of type '<class 'numpy.float64'>'\n",
       "\twith 8000975 stored elements in Compressed Sparse Row format>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "URM_train"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What do we need for a SLIM MSE?\n",
    "\n",
    "* Item-Item similarity matrix\n",
    "* Computing prediction\n",
    "* Update rule\n",
    "* Training loop and some patience\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_users, n_items = URM_train.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 1: We create a dense similarity matrix, initialized as zero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0., 0., 0., ..., 0., 0., 0.],\n",
       "       [0., 0., 0., ..., 0., 0., 0.],\n",
       "       [0., 0., 0., ..., 0., 0., 0.],\n",
       "       ...,\n",
       "       [0., 0., 0., ..., 0., 0., 0.],\n",
       "       [0., 0., 0., ..., 0., 0., 0.],\n",
       "       [0., 0., 0., ..., 0., 0., 0.]])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "item_item_S = np.zeros((n_items, n_items), dtype = np.float)\n",
    "item_item_S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 2: We sample an interaction and compute the prediction of the current SLIM model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3787221"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "URM_train_coo = URM_train.tocoo()\n",
    "\n",
    "sample_index = np.random.randint(URM_train_coo.nnz)\n",
    "sample_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(33017, 279, 5.0)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "user_id = URM_train_coo.row[sample_index]\n",
    "item_id = URM_train_coo.col[sample_index]\n",
    "true_rating = URM_train_coo.data[sample_index]\n",
    "\n",
    "(user_id, item_id, true_rating)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predicted_rating = URM_train[user_id].dot(item_item_S[:,item_id])[0]\n",
    "predicted_rating"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The first predicted rating is zero, of course, the model is \"empty\"\n",
    "\n",
    "### Step 3: We compute the prediction error and update the item-item similarity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.0"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prediction_error = true_rating - predicted_rating\n",
    "prediction_error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The error is positive, so we need to increase the prediction our model computes. Meaning, we have to increase the values in the item-item similarity matrix\n",
    "\n",
    "### Which item similarities we modify? Only those we used to compute the prediction, i.e., only the items in the profile of the sampled user. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([   2,    3,    4,    5,    7,    9,   11,   14,   16,   17,   18,\n",
       "         19,   20,   22,   24,   26,   27,   31,   32,   33,   34,   35,\n",
       "         36,   37,   38,   40,   43,   48,   51,   52,   55,   56,   60,\n",
       "         61,   62,   63,   71,   74,   77,   78,   79,   81,   82,   84,\n",
       "         85,   91,   93,   94,   95,   96,   97,  101,  102,  130,  133,\n",
       "        139,  146,  147,  148,  156,  163,  165,  171,  175,  176,  177,\n",
       "        178,  179,  183,  185,  186,  187,  188,  190,  192,  195,  197,\n",
       "        198,  199,  201,  202,  204,  206,  209,  212,  213,  234,  235,\n",
       "        238,  241,  242,  244,  245,  246,  248,  252,  258,  259,  261,\n",
       "        271,  277,  279,  284,  285,  292,  294,  296,  301,  302,  309,\n",
       "        312,  315,  321,  323,  324,  329,  331,  336,  338,  340,  345,\n",
       "        346,  358,  369,  373,  377,  380,  385,  389,  390,  391,  401,\n",
       "        402,  403,  406,  411,  413,  415,  416,  417,  418,  420,  422,\n",
       "        423,  425,  426,  428,  436,  437,  440,  444,  447,  451,  454,\n",
       "        455,  460,  461,  466,  468,  473,  475,  476,  481,  482,  483,\n",
       "        485,  487,  499,  500,  501,  504,  505,  509,  513,  517,  519,\n",
       "        526,  527,  528,  529,  533,  534,  535,  536,  538,  540,  543,\n",
       "        545,  546,  554,  555,  557,  559,  563,  565,  568,  577,  584,\n",
       "        585,  589,  591,  592,  602,  603,  604,  605,  606,  610,  611,\n",
       "        612,  616,  620,  624,  627,  629,  630,  631,  633,  635,  636,\n",
       "        638,  646,  656,  658,  667,  668,  670,  677,  683,  684,  687,\n",
       "        689,  691,  694,  700,  701,  702,  704,  705,  717,  718,  722,\n",
       "        726,  728,  730,  731,  740,  743,  745,  748,  750,  755,  758,\n",
       "        763,  767,  770,  772,  774,  775,  792,  793,  798,  799,  804,\n",
       "        808,  810,  811,  812,  813,  815,  818,  821,  822,  825,  826,\n",
       "        828,  830,  835,  838,  839,  846,  851,  863,  864,  866,  867,\n",
       "        874,  876,  879,  886,  896,  899,  902,  904,  932,  936,  995,\n",
       "       1005, 1008, 1009, 1032, 1033, 1040, 1041, 1043, 1046, 1048, 1074,\n",
       "       1077, 1078, 1079, 1080, 1081, 1083, 1092, 1093, 1096, 1101, 1112,\n",
       "       1118, 1131, 1138, 1147, 1158, 1171, 1174, 1177, 1179, 1181, 1183,\n",
       "       1190, 1192, 1197, 1201, 1204, 1207, 1211, 1212, 1213, 1215, 1254,\n",
       "       1257, 1259, 1269, 1272, 1273, 1280, 1281, 1283, 1287, 1293, 1298,\n",
       "       1299, 1300, 1303, 1304, 1311, 1323, 1329, 1330, 1331, 1333, 1347,\n",
       "       1350, 1351, 1352, 1360, 1365, 1368, 1370, 1375, 1383, 1384, 1386,\n",
       "       1407, 1423, 1425, 1427, 1428, 1433, 1468, 1469, 1470, 1472, 1473,\n",
       "       1497, 1499, 1521, 1528, 1539, 1547, 1558, 1576, 1585, 1590, 1636,\n",
       "       1650, 1652, 1667, 1670, 1672, 1682, 1716, 1717, 1730, 1737, 1741,\n",
       "       1743, 1754, 1759, 1762, 1763, 1770, 1797, 1805, 1808, 1812, 1815,\n",
       "       1821, 1826, 1846, 1855, 1858, 1861, 1863, 1873, 1876, 1884, 1890,\n",
       "       1899, 1904, 1906, 1920, 1987, 1989, 2010, 2015, 2048, 2056, 2066,\n",
       "       2095, 2151, 2187, 2214, 2275, 2292, 2305, 2340, 2358, 2479, 2536,\n",
       "       2540, 2574, 2594, 2595, 2598, 2606, 2612, 2646, 2677, 2735, 2840,\n",
       "       2945, 2947, 2965, 3018, 3096, 3116, 3117, 3223, 3250, 3318, 3326,\n",
       "       3330, 3336, 3340, 3406, 3410, 3526, 3536, 3601, 3609, 3632, 3653,\n",
       "       3688, 3713, 3784, 3798, 3816, 3858, 4002, 4072, 4088, 4094, 4193,\n",
       "       4357, 4747, 4971, 5010, 5036, 5182, 5329, 5398, 5666, 5690, 6021,\n",
       "       6255, 6335, 6393, 7172, 8278, 8430])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "items_in_user_profile = URM_train[user_id].indices\n",
    "items_in_user_profile"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([3. , 3.5, 3. , 3. , 5. , 5. , 3.5, 5. , 4. , 4. , 4. , 5. , 4. ,\n",
       "       5. , 5. , 5. , 4. , 3. , 4. , 3.5, 5. , 4. , 4. , 5. , 4. , 4. ,\n",
       "       4.5, 3.5, 4. , 4. , 3. , 4. , 4.5, 3.5, 5. , 4.5, 4. , 4. , 4. ,\n",
       "       4. , 4. , 3. , 4. , 3. , 4.5, 4. , 5. , 4. , 4. , 5. , 4. , 4. ,\n",
       "       4.5, 5. , 5. , 5. , 5. , 5. , 5. , 5. , 4.5, 5. , 5. , 5. , 4. ,\n",
       "       5. , 5. , 5. , 5. , 4. , 3. , 3.5, 4. , 4. , 5. , 5. , 3.5, 5. ,\n",
       "       4. , 4. , 3.5, 3. , 5. , 3.5, 3. , 5. , 5. , 5. , 4. , 4.5, 4.5,\n",
       "       5. , 4. , 4. , 3.5, 3.5, 4. , 5. , 5. , 4. , 5. , 5. , 4. , 3. ,\n",
       "       4. , 3.5, 4. , 3. , 5. , 3.5, 4. , 4. , 3. , 3. , 4. , 4. , 3. ,\n",
       "       4. , 4. , 3. , 3. , 3. , 4. , 3. , 3. , 2. , 4. , 3. , 4. , 4. ,\n",
       "       3.5, 5. , 3. , 3. , 4. , 4. , 4. , 5. , 4. , 4.5, 3. , 3.5, 4. ,\n",
       "       3.5, 4. , 5. , 4. , 1. , 5. , 1. , 2.5, 4. , 4.5, 3. , 3. , 4. ,\n",
       "       4. , 4.5, 4. , 4.5, 3. , 3. , 3.5, 3. , 3. , 4. , 5. , 4. , 4. ,\n",
       "       4. , 4. , 4. , 4. , 4. , 3. , 4.5, 4. , 4. , 4. , 3. , 4.5, 3. ,\n",
       "       4. , 3. , 3. , 4. , 4. , 4. , 3. , 3. , 3. , 2. , 3.5, 3.5, 4. ,\n",
       "       4. , 3.5, 4.5, 3. , 4. , 3. , 3. , 3. , 4. , 4. , 5. , 3. , 3. ,\n",
       "       4.5, 5. , 5. , 4. , 2. , 3.5, 3. , 3. , 3. , 4. , 4. , 4. , 3.5,\n",
       "       4. , 3. , 3. , 4. , 5. , 3. , 4. , 3. , 2. , 4. , 3. , 4. , 4. ,\n",
       "       3. , 2.5, 3. , 3. , 4.5, 2. , 4. , 4.5, 4. , 2.5, 4. , 3.5, 3. ,\n",
       "       3.5, 3. , 3. , 4. , 3. , 4. , 3. , 4. , 3. , 3. , 4. , 3. , 3. ,\n",
       "       4.5, 5. , 4. , 4. , 3. , 4.5, 3. , 3. , 3. , 3. , 3.5, 4. , 4. ,\n",
       "       4. , 4. , 3. , 3. , 3. , 3. , 2. , 4. , 3. , 3.5, 4. , 4. , 3.5,\n",
       "       3.5, 4. , 3. , 3. , 3.5, 4.5, 4. , 3.5, 4. , 3.5, 3. , 3. , 4.5,\n",
       "       3. , 3. , 4. , 3. , 4.5, 2. , 4. , 4. , 3. , 4. , 4. , 3.5, 5. ,\n",
       "       4. , 3.5, 4. , 5. , 4. , 3. , 2. , 3. , 3. , 4.5, 4. , 3. , 4. ,\n",
       "       3.5, 4. , 3. , 4. , 4. , 4. , 5. , 4. , 4.5, 4.5, 3. , 4. , 4. ,\n",
       "       3.5, 2.5, 4. , 4. , 3.5, 4. , 3.5, 3. , 4. , 4.5, 3. , 2.5, 5. ,\n",
       "       3. , 3. , 3. , 4. , 4. , 3. , 3. , 2. , 2. , 4. , 4. , 2. , 4. ,\n",
       "       4. , 3. , 4.5, 4.5, 4. , 4. , 4. , 2. , 3. , 4. , 2. , 3. , 3.5,\n",
       "       4. , 4. , 3. , 4.5, 3. , 4. , 3. , 3.5, 3. , 4. , 2. , 3. , 4.5,\n",
       "       3. , 4. , 3. , 1. , 3. , 4. , 2. , 2. , 4. , 4. , 3. , 4. , 5. ,\n",
       "       4. , 3. , 2. , 3.5, 4. , 4. , 3. , 3. , 4.5, 2. , 1. , 3. , 3. ,\n",
       "       4. , 4. , 3.5, 3.5, 4. , 3. , 4.5, 4. , 4. , 3. , 4. , 2.5, 4.5,\n",
       "       3. , 4. , 3. , 5. , 3. , 4. , 3.5, 3.5, 2. , 3. , 4. , 3. , 4. ,\n",
       "       4.5, 3. , 3.5, 2.5, 4.5, 4. , 4. , 2.5, 3. , 3. , 3. , 5. , 4. ,\n",
       "       3. , 5. , 4. , 5. , 2. , 3.5, 4.5, 3. , 3.5, 4. , 3. , 4. , 4. ,\n",
       "       3. , 3. , 2. , 2. , 3. , 3.5, 4. , 4. , 3. , 3. , 3. , 3. , 2. ,\n",
       "       4. , 4. , 3. , 3. , 4. , 3.5, 4. , 3. , 4. , 2.5, 3. , 3. , 3. ,\n",
       "       3. , 3. , 1. , 3. , 4. , 4. , 4. , 4. , 3. , 3. , 5. , 3. , 3. ,\n",
       "       5. , 3. , 3. , 3. , 4. ])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ratings_in_user_profile = URM_train[user_id].data\n",
    "ratings_in_user_profile"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Apply the update rule"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,\n",
       "       0., 0.])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "item_item_S[items_in_user_profile,item_id]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "learning_rate = 1e-4\n",
    "\n",
    "item_item_S[items_in_user_profile,item_id] += learning_rate * prediction_error * ratings_in_user_profile"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.0015 , 0.00175, 0.0015 , 0.0015 , 0.0025 , 0.0025 , 0.00175,\n",
       "       0.0025 , 0.002  , 0.002  , 0.002  , 0.0025 , 0.002  , 0.0025 ,\n",
       "       0.0025 , 0.0025 , 0.002  , 0.0015 , 0.002  , 0.00175, 0.0025 ,\n",
       "       0.002  , 0.002  , 0.0025 , 0.002  , 0.002  , 0.00225, 0.00175,\n",
       "       0.002  , 0.002  , 0.0015 , 0.002  , 0.00225, 0.00175, 0.0025 ,\n",
       "       0.00225, 0.002  , 0.002  , 0.002  , 0.002  , 0.002  , 0.0015 ,\n",
       "       0.002  , 0.0015 , 0.00225, 0.002  , 0.0025 , 0.002  , 0.002  ,\n",
       "       0.0025 , 0.002  , 0.002  , 0.00225, 0.0025 , 0.0025 , 0.0025 ,\n",
       "       0.0025 , 0.0025 , 0.0025 , 0.0025 , 0.00225, 0.0025 , 0.0025 ,\n",
       "       0.0025 , 0.002  , 0.0025 , 0.0025 , 0.0025 , 0.0025 , 0.002  ,\n",
       "       0.0015 , 0.00175, 0.002  , 0.002  , 0.0025 , 0.0025 , 0.00175,\n",
       "       0.0025 , 0.002  , 0.002  , 0.00175, 0.0015 , 0.0025 , 0.00175,\n",
       "       0.0015 , 0.0025 , 0.0025 , 0.0025 , 0.002  , 0.00225, 0.00225,\n",
       "       0.0025 , 0.002  , 0.002  , 0.00175, 0.00175, 0.002  , 0.0025 ,\n",
       "       0.0025 , 0.002  , 0.0025 , 0.0025 , 0.002  , 0.0015 , 0.002  ,\n",
       "       0.00175, 0.002  , 0.0015 , 0.0025 , 0.00175, 0.002  , 0.002  ,\n",
       "       0.0015 , 0.0015 , 0.002  , 0.002  , 0.0015 , 0.002  , 0.002  ,\n",
       "       0.0015 , 0.0015 , 0.0015 , 0.002  , 0.0015 , 0.0015 , 0.001  ,\n",
       "       0.002  , 0.0015 , 0.002  , 0.002  , 0.00175, 0.0025 , 0.0015 ,\n",
       "       0.0015 , 0.002  , 0.002  , 0.002  , 0.0025 , 0.002  , 0.00225,\n",
       "       0.0015 , 0.00175, 0.002  , 0.00175, 0.002  , 0.0025 , 0.002  ,\n",
       "       0.0005 , 0.0025 , 0.0005 , 0.00125, 0.002  , 0.00225, 0.0015 ,\n",
       "       0.0015 , 0.002  , 0.002  , 0.00225, 0.002  , 0.00225, 0.0015 ,\n",
       "       0.0015 , 0.00175, 0.0015 , 0.0015 , 0.002  , 0.0025 , 0.002  ,\n",
       "       0.002  , 0.002  , 0.002  , 0.002  , 0.002  , 0.002  , 0.0015 ,\n",
       "       0.00225, 0.002  , 0.002  , 0.002  , 0.0015 , 0.00225, 0.0015 ,\n",
       "       0.002  , 0.0015 , 0.0015 , 0.002  , 0.002  , 0.002  , 0.0015 ,\n",
       "       0.0015 , 0.0015 , 0.001  , 0.00175, 0.00175, 0.002  , 0.002  ,\n",
       "       0.00175, 0.00225, 0.0015 , 0.002  , 0.0015 , 0.0015 , 0.0015 ,\n",
       "       0.002  , 0.002  , 0.0025 , 0.0015 , 0.0015 , 0.00225, 0.0025 ,\n",
       "       0.0025 , 0.002  , 0.001  , 0.00175, 0.0015 , 0.0015 , 0.0015 ,\n",
       "       0.002  , 0.002  , 0.002  , 0.00175, 0.002  , 0.0015 , 0.0015 ,\n",
       "       0.002  , 0.0025 , 0.0015 , 0.002  , 0.0015 , 0.001  , 0.002  ,\n",
       "       0.0015 , 0.002  , 0.002  , 0.0015 , 0.00125, 0.0015 , 0.0015 ,\n",
       "       0.00225, 0.001  , 0.002  , 0.00225, 0.002  , 0.00125, 0.002  ,\n",
       "       0.00175, 0.0015 , 0.00175, 0.0015 , 0.0015 , 0.002  , 0.0015 ,\n",
       "       0.002  , 0.0015 , 0.002  , 0.0015 , 0.0015 , 0.002  , 0.0015 ,\n",
       "       0.0015 , 0.00225, 0.0025 , 0.002  , 0.002  , 0.0015 , 0.00225,\n",
       "       0.0015 , 0.0015 , 0.0015 , 0.0015 , 0.00175, 0.002  , 0.002  ,\n",
       "       0.002  , 0.002  , 0.0015 , 0.0015 , 0.0015 , 0.0015 , 0.001  ,\n",
       "       0.002  , 0.0015 , 0.00175, 0.002  , 0.002  , 0.00175, 0.00175,\n",
       "       0.002  , 0.0015 , 0.0015 , 0.00175, 0.00225, 0.002  , 0.00175,\n",
       "       0.002  , 0.00175, 0.0015 , 0.0015 , 0.00225, 0.0015 , 0.0015 ,\n",
       "       0.002  , 0.0015 , 0.00225, 0.001  , 0.002  , 0.002  , 0.0015 ,\n",
       "       0.002  , 0.002  , 0.00175, 0.0025 , 0.002  , 0.00175, 0.002  ,\n",
       "       0.0025 , 0.002  , 0.0015 , 0.001  , 0.0015 , 0.0015 , 0.00225,\n",
       "       0.002  , 0.0015 , 0.002  , 0.00175, 0.002  , 0.0015 , 0.002  ,\n",
       "       0.002  , 0.002  , 0.0025 , 0.002  , 0.00225, 0.00225, 0.0015 ,\n",
       "       0.002  , 0.002  , 0.00175, 0.00125, 0.002  , 0.002  , 0.00175,\n",
       "       0.002  , 0.00175, 0.0015 , 0.002  , 0.00225, 0.0015 , 0.00125,\n",
       "       0.0025 , 0.0015 , 0.0015 , 0.0015 , 0.002  , 0.002  , 0.0015 ,\n",
       "       0.0015 , 0.001  , 0.001  , 0.002  , 0.002  , 0.001  , 0.002  ,\n",
       "       0.002  , 0.0015 , 0.00225, 0.00225, 0.002  , 0.002  , 0.002  ,\n",
       "       0.001  , 0.0015 , 0.002  , 0.001  , 0.0015 , 0.00175, 0.002  ,\n",
       "       0.002  , 0.0015 , 0.00225, 0.0015 , 0.002  , 0.0015 , 0.00175,\n",
       "       0.0015 , 0.002  , 0.001  , 0.0015 , 0.00225, 0.0015 , 0.002  ,\n",
       "       0.0015 , 0.0005 , 0.0015 , 0.002  , 0.001  , 0.001  , 0.002  ,\n",
       "       0.002  , 0.0015 , 0.002  , 0.0025 , 0.002  , 0.0015 , 0.001  ,\n",
       "       0.00175, 0.002  , 0.002  , 0.0015 , 0.0015 , 0.00225, 0.001  ,\n",
       "       0.0005 , 0.0015 , 0.0015 , 0.002  , 0.002  , 0.00175, 0.00175,\n",
       "       0.002  , 0.0015 , 0.00225, 0.002  , 0.002  , 0.0015 , 0.002  ,\n",
       "       0.00125, 0.00225, 0.0015 , 0.002  , 0.0015 , 0.0025 , 0.0015 ,\n",
       "       0.002  , 0.00175, 0.00175, 0.001  , 0.0015 , 0.002  , 0.0015 ,\n",
       "       0.002  , 0.00225, 0.0015 , 0.00175, 0.00125, 0.00225, 0.002  ,\n",
       "       0.002  , 0.00125, 0.0015 , 0.0015 , 0.0015 , 0.0025 , 0.002  ,\n",
       "       0.0015 , 0.0025 , 0.002  , 0.0025 , 0.001  , 0.00175, 0.00225,\n",
       "       0.0015 , 0.00175, 0.002  , 0.0015 , 0.002  , 0.002  , 0.0015 ,\n",
       "       0.0015 , 0.001  , 0.001  , 0.0015 , 0.00175, 0.002  , 0.002  ,\n",
       "       0.0015 , 0.0015 , 0.0015 , 0.0015 , 0.001  , 0.002  , 0.002  ,\n",
       "       0.0015 , 0.0015 , 0.002  , 0.00175, 0.002  , 0.0015 , 0.002  ,\n",
       "       0.00125, 0.0015 , 0.0015 , 0.0015 , 0.0015 , 0.0015 , 0.0005 ,\n",
       "       0.0015 , 0.002  , 0.002  , 0.002  , 0.002  , 0.0015 , 0.0015 ,\n",
       "       0.0025 , 0.0015 , 0.0015 , 0.0025 , 0.0015 , 0.0015 , 0.0015 ,\n",
       "       0.002  ])"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "item_item_S[items_in_user_profile,item_id]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's check what the new prediction for the same user-item interaction would be"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.6118750000000057"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predicted_rating = URM_train[user_id].dot(item_item_S[:,item_id])[0]\n",
    "predicted_rating"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The value is not zero anymore, but higher, we are moving in the right direction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### And now? Sample another interaction and repeat... a lot of times"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's put all together in a training loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 5000 in 2.52 seconds, loss is 13.49. Samples per second 1981.70\n",
      "Iteration 10000 in 4.51 seconds, loss is 13.41. Samples per second 2216.32\n",
      "Iteration 15000 in 6.53 seconds, loss is 13.37. Samples per second 2295.72\n",
      "Iteration 20000 in 8.51 seconds, loss is 13.35. Samples per second 2349.94\n",
      "Iteration 25000 in 10.50 seconds, loss is 13.31. Samples per second 2381.21\n",
      "Iteration 30000 in 12.49 seconds, loss is 13.29. Samples per second 2402.15\n",
      "Iteration 35000 in 14.49 seconds, loss is 13.27. Samples per second 2415.33\n",
      "Iteration 40000 in 16.42 seconds, loss is 13.24. Samples per second 2435.49\n",
      "Iteration 45000 in 18.55 seconds, loss is 13.20. Samples per second 2426.42\n",
      "Iteration 50000 in 20.67 seconds, loss is 13.17. Samples per second 2419.29\n",
      "Iteration 55000 in 22.80 seconds, loss is 13.16. Samples per second 2412.33\n",
      "Iteration 60000 in 24.88 seconds, loss is 13.14. Samples per second 2411.42\n",
      "Iteration 65000 in 26.83 seconds, loss is 13.12. Samples per second 2422.83\n",
      "Iteration 70000 in 29.35 seconds, loss is 13.09. Samples per second 2385.15\n",
      "Iteration 75000 in 31.75 seconds, loss is 13.05. Samples per second 2361.86\n",
      "Iteration 80000 in 34.21 seconds, loss is 13.04. Samples per second 2338.65\n",
      "Iteration 85000 in 36.51 seconds, loss is 13.02. Samples per second 2327.87\n",
      "Iteration 90000 in 38.60 seconds, loss is 12.99. Samples per second 2331.32\n",
      "Iteration 95000 in 40.63 seconds, loss is 12.95. Samples per second 2337.89\n",
      "Iteration 100000 in 42.65 seconds, loss is 12.93. Samples per second 2344.67\n"
     ]
    }
   ],
   "source": [
    "URM_train_coo = URM_train.tocoo()\n",
    "item_item_S = np.zeros((n_items, n_items), dtype = np.float)\n",
    "\n",
    "learning_rate = 1e-6\n",
    "\n",
    "loss = 0.0\n",
    "start_time = time.time()\n",
    "for sample_num in range(100000):\n",
    "    \n",
    "    # Randomly pick sample\n",
    "    sample_index = np.random.randint(URM_train_coo.nnz)\n",
    "\n",
    "    user_id = URM_train_coo.row[sample_index]\n",
    "    item_id = URM_train_coo.col[sample_index]\n",
    "    true_rating = URM_train_coo.data[sample_index]\n",
    "\n",
    "    # Compute prediction\n",
    "    predicted_rating = URM_train[user_id].dot(item_item_S[:,item_id])[0]\n",
    "        \n",
    "    # Compute prediction error, or gradient\n",
    "    prediction_error = true_rating - predicted_rating\n",
    "    loss += prediction_error**2\n",
    "    \n",
    "    # Update model, in this case the similarity\n",
    "    items_in_user_profile = URM_train[user_id].indices\n",
    "    ratings_in_user_profile = URM_train[user_id].data\n",
    "    item_item_S[items_in_user_profile,item_id] += learning_rate * prediction_error * ratings_in_user_profile\n",
    "    \n",
    "    # Print some stats\n",
    "    if (sample_num +1)% 5000 == 0:\n",
    "        elapsed_time = time.time() - start_time\n",
    "        samples_per_second = (sample_num +1)/elapsed_time\n",
    "        print(\"Iteration {} in {:.2f} seconds, loss is {:.2f}. Samples per second {:.2f}\".format(sample_num+1, elapsed_time, loss/(sample_num +1), samples_per_second))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What do we see? The loss oscillates over time, sometimes it goes down sometimes up.\n",
    "### How long do we train such a model?\n",
    "\n",
    "* An epoch: a complete loop over all the train data\n",
    "* Usually you train for multiple epochs. Depending on the algorithm and data 10s or 100s of epochs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def train_one_epoch(URM_train, item_item_S, learning_rate):\n",
    "    \n",
    "    URM_train_coo = URM_train.tocoo()\n",
    "\n",
    "    loss = 0.0\n",
    "    start_time = time.time()\n",
    "    for sample_num in range(URM_train.nnz):\n",
    "\n",
    "        # Randomly pick sample\n",
    "        sample_index = np.random.randint(URM_train_coo.nnz)\n",
    "\n",
    "        user_id = URM_train_coo.row[sample_index]\n",
    "        item_id = URM_train_coo.col[sample_index]\n",
    "        true_rating = URM_train_coo.data[sample_index]\n",
    "\n",
    "        # Compute prediction\n",
    "        predicted_rating = URM_train[user_id].dot(item_item_S[:,item_id])[0]\n",
    "\n",
    "        # Compute prediction error, or gradient\n",
    "        prediction_error = true_rating - predicted_rating\n",
    "        loss += prediction_error**2\n",
    "\n",
    "        # Update model, in this case the similarity\n",
    "        items_in_user_profile = URM_train[user_id].indices\n",
    "        ratings_in_user_profile = URM_train[user_id].data\n",
    "        item_item_S[items_in_user_profile,item_id] += learning_rate * prediction_error * ratings_in_user_profile\n",
    "\n",
    "        # Print some stats\n",
    "        if (sample_num +1)% 5000 == 0:\n",
    "            elapsed_time = time.time() - start_time\n",
    "            samples_per_second = (sample_num +1)/elapsed_time\n",
    "            print(\"Iteration {} in {:.2f} seconds, loss is {:.2f}. Samples per second {:.2f}\".format(sample_num+1, elapsed_time, loss/(sample_num +1), samples_per_second))\n",
    "         \n",
    "            # Stop training because this implementation is too slow\n",
    "            print(\"\\tStopping the epoch early because this implementation is too slow\")\n",
    "            return item_item_S\n",
    "            \n",
    "    return item_item_S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 5000 in 2.20 seconds, loss is 13.45. Samples per second 2271.72\n",
      "\tStopping the epoch early because this implementation is too slow\n",
      "Iteration 5000 in 1.94 seconds, loss is 13.44. Samples per second 2583.97\n",
      "\tStopping the epoch early because this implementation is too slow\n",
      "Iteration 5000 in 1.93 seconds, loss is 13.30. Samples per second 2586.25\n",
      "\tStopping the epoch early because this implementation is too slow\n",
      "Iteration 5000 in 1.91 seconds, loss is 13.24. Samples per second 2620.69\n",
      "\tStopping the epoch early because this implementation is too slow\n",
      "Iteration 5000 in 1.94 seconds, loss is 13.35. Samples per second 2582.58\n",
      "\tStopping the epoch early because this implementation is too slow\n"
     ]
    }
   ],
   "source": [
    "n_items = URM_train.shape[1]\n",
    "learning_rate = 1e-6\n",
    "    \n",
    "item_item_S = np.zeros((n_items, n_items), dtype = np.float)\n",
    "\n",
    "for n_epoch in range(5):\n",
    "    item_item_S = train_one_epoch(URM_train, item_item_S, learning_rate)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[2.99929130e-05, 5.32433053e-05, 4.63581199e-05, ...,\n",
       "        0.00000000e+00, 0.00000000e+00, 0.00000000e+00],\n",
       "       [1.09904936e-05, 5.99211075e-04, 2.12381781e-04, ...,\n",
       "        0.00000000e+00, 0.00000000e+00, 0.00000000e+00],\n",
       "       [1.99923892e-05, 2.49503284e-04, 5.10311713e-04, ...,\n",
       "        0.00000000e+00, 0.00000000e+00, 0.00000000e+00],\n",
       "       ...,\n",
       "       [0.00000000e+00, 0.00000000e+00, 0.00000000e+00, ...,\n",
       "        0.00000000e+00, 0.00000000e+00, 0.00000000e+00],\n",
       "       [0.00000000e+00, 0.00000000e+00, 0.00000000e+00, ...,\n",
       "        0.00000000e+00, 0.00000000e+00, 0.00000000e+00],\n",
       "       [0.00000000e+00, 0.00000000e+00, 0.00000000e+00, ...,\n",
       "        0.00000000e+00, 0.00000000e+00, 0.00000000e+00]])"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "item_item_S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### How do we use this similarity? As in a simple item-based KNN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's estimate the training time. Say we train for 10 epochs and we have 8M interactions in the train data..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated time with the previous training speed is 34120.00 seconds, or 568.67 minutes\n"
     ]
    }
   ],
   "source": [
    "estimated_seconds = 8e6 * 10 / samples_per_second\n",
    "print(\"Estimated time with the previous training speed is {:.2f} seconds, or {:.2f} minutes\".format(estimated_seconds, estimated_seconds/60))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ... ehm, 10 hours\n",
    "### Unacceptable!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's rewrite the loop with some smarter use of the data structures. In particular:\n",
    "* Use the indptr/indices data structures to get the seen items\n",
    "* Not much else we can do with this tools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 5000 in 1.64 seconds, loss is 13.36. Samples per second 3046.01\n",
      "Iteration 10000 in 3.09 seconds, loss is 13.36. Samples per second 3236.43\n",
      "Iteration 15000 in 4.48 seconds, loss is 13.35. Samples per second 3349.89\n",
      "Iteration 20000 in 5.88 seconds, loss is 13.34. Samples per second 3401.82\n",
      "Iteration 25000 in 7.30 seconds, loss is 13.31. Samples per second 3423.59\n",
      "Iteration 30000 in 8.74 seconds, loss is 13.27. Samples per second 3432.38\n",
      "Iteration 35000 in 10.16 seconds, loss is 13.22. Samples per second 3444.04\n",
      "Iteration 40000 in 11.60 seconds, loss is 13.19. Samples per second 3448.66\n",
      "Iteration 45000 in 13.00 seconds, loss is 13.17. Samples per second 3460.66\n",
      "Iteration 50000 in 14.43 seconds, loss is 13.15. Samples per second 3463.92\n",
      "Iteration 55000 in 15.83 seconds, loss is 13.12. Samples per second 3474.56\n",
      "Iteration 60000 in 17.26 seconds, loss is 13.10. Samples per second 3475.42\n",
      "Iteration 65000 in 18.68 seconds, loss is 13.07. Samples per second 3480.08\n",
      "Iteration 70000 in 20.07 seconds, loss is 13.05. Samples per second 3488.36\n",
      "Iteration 75000 in 21.52 seconds, loss is 13.03. Samples per second 3485.12\n",
      "Iteration 80000 in 23.00 seconds, loss is 12.99. Samples per second 3477.62\n",
      "Iteration 85000 in 24.40 seconds, loss is 12.97. Samples per second 3483.75\n",
      "Iteration 90000 in 25.87 seconds, loss is 12.95. Samples per second 3478.86\n",
      "Iteration 95000 in 27.29 seconds, loss is 12.92. Samples per second 3481.37\n",
      "Iteration 100000 in 28.72 seconds, loss is 12.90. Samples per second 3481.91\n"
     ]
    }
   ],
   "source": [
    "URM_train_coo = URM_train.tocoo()\n",
    "item_item_S = np.zeros((n_items, n_items), dtype = np.float)\n",
    "\n",
    "learning_rate = 1e-6\n",
    "\n",
    "loss = 0.0\n",
    "start_time = time.time()\n",
    "for sample_num in range(100000):\n",
    "    \n",
    "    # Randomly pick sample\n",
    "    sample_index = np.random.randint(URM_train_coo.nnz)\n",
    "\n",
    "    user_id = URM_train_coo.row[sample_index]\n",
    "    item_id = URM_train_coo.col[sample_index]\n",
    "    true_rating = URM_train_coo.data[sample_index]\n",
    "\n",
    "    # Compute prediction\n",
    "    predicted_rating = URM_train[user_id].dot(item_item_S[:,item_id])[0]\n",
    "        \n",
    "    # Compute prediction error, or gradient\n",
    "    prediction_error = true_rating - predicted_rating\n",
    "    loss += prediction_error**2\n",
    "    \n",
    "    # Update model, in this case the similarity\n",
    "    items_in_user_profile = URM_train.indices[URM_train.indptr[user_id]:URM_train.indptr[user_id+1]]\n",
    "    ratings_in_user_profile = URM_train.data[URM_train.indptr[user_id]:URM_train.indptr[user_id+1]]\n",
    "    item_item_S[items_in_user_profile,item_id] += learning_rate * prediction_error * ratings_in_user_profile\n",
    "    \n",
    "    # Print some stats\n",
    "    if (sample_num +1)% 5000 == 0:\n",
    "        elapsed_time = time.time() - start_time\n",
    "        samples_per_second = (sample_num +1)/elapsed_time\n",
    "        print(\"Iteration {} in {:.2f} seconds, loss is {:.2f}. Samples per second {:.2f}\".format(sample_num+1, elapsed_time, loss/(sample_num +1), samples_per_second))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated time with the previous training speed is 22975.86 seconds, or 382.93 minutes\n"
     ]
    }
   ],
   "source": [
    "estimated_seconds = 8e6 * 10 / samples_per_second\n",
    "print(\"Estimated time with the previous training speed is {:.2f} seconds, or {:.2f} minutes\".format(estimated_seconds, estimated_seconds/60))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### We now got 7 hours, just as bad as before\n",
    "\n",
    "### Let's see what we can do with Cython\n",
    "### First step, just compile it. We do not have the data at compile time, so we put the loop in a function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "import numpy as np\n",
    "import time\n",
    "\n",
    "def do_some_training(URM_train):\n",
    "    \n",
    "    URM_train_coo = URM_train.tocoo()\n",
    "    n_items = URM_train.shape[1]\n",
    "    \n",
    "    item_item_S = np.zeros((n_items, n_items), dtype = np.float16)\n",
    "\n",
    "    learning_rate = 1e-6\n",
    "\n",
    "    loss = 0.0\n",
    "    start_time = time.time()\n",
    "    for sample_num in range(100000):\n",
    "\n",
    "        # Randomly pick sample\n",
    "        sample_index = np.random.randint(URM_train_coo.nnz)\n",
    "\n",
    "        user_id = URM_train_coo.row[sample_index]\n",
    "        item_id = URM_train_coo.col[sample_index]\n",
    "        true_rating = URM_train_coo.data[sample_index]\n",
    "\n",
    "        # Compute prediction\n",
    "        predicted_rating = URM_train[user_id].dot(item_item_S[:,item_id])[0]\n",
    "\n",
    "        # Compute prediction error, or gradient\n",
    "        prediction_error = true_rating - predicted_rating\n",
    "        loss += prediction_error**2\n",
    "\n",
    "        # Update model, in this case the similarity\n",
    "        items_in_user_profile = URM_train.indices[URM_train.indptr[user_id]:URM_train.indptr[user_id+1]]\n",
    "        ratings_in_user_profile = URM_train.data[URM_train.indptr[user_id]:URM_train.indptr[user_id+1]]\n",
    "        item_item_S[items_in_user_profile,item_id] += learning_rate * prediction_error * ratings_in_user_profile\n",
    "\n",
    "        # Print some stats\n",
    "        if (sample_num +1)% 5000 == 0:\n",
    "            elapsed_time = time.time() - start_time\n",
    "            samples_per_second = (sample_num +1)/elapsed_time\n",
    "            print(\"Iteration {} in {:.2f} seconds, loss is {:.2f}. Samples per second {:.2f}\".format(sample_num+1, elapsed_time, loss/(sample_num +1), samples_per_second))\n",
    "    \n",
    "    return loss, samples_per_second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 5000 in 1.43 seconds, loss is 13.38. Samples per second 3505.21\n",
      "Iteration 10000 in 2.86 seconds, loss is 13.34. Samples per second 3501.29\n",
      "Iteration 15000 in 4.30 seconds, loss is 13.30. Samples per second 3488.81\n",
      "Iteration 20000 in 5.71 seconds, loss is 13.30. Samples per second 3500.03\n",
      "Iteration 25000 in 7.20 seconds, loss is 13.30. Samples per second 3473.65\n",
      "Iteration 30000 in 8.61 seconds, loss is 13.28. Samples per second 3484.30\n",
      "Iteration 35000 in 10.06 seconds, loss is 13.24. Samples per second 3478.57\n",
      "Iteration 40000 in 11.56 seconds, loss is 13.22. Samples per second 3459.54\n",
      "Iteration 45000 in 13.01 seconds, loss is 13.20. Samples per second 3457.90\n",
      "Iteration 50000 in 14.45 seconds, loss is 13.18. Samples per second 3459.66\n",
      "Iteration 55000 in 15.91 seconds, loss is 13.14. Samples per second 3457.15\n",
      "Iteration 60000 in 17.38 seconds, loss is 13.10. Samples per second 3453.15\n",
      "Iteration 65000 in 18.88 seconds, loss is 13.08. Samples per second 3442.80\n",
      "Iteration 70000 in 20.35 seconds, loss is 13.06. Samples per second 3439.85\n",
      "Iteration 75000 in 21.84 seconds, loss is 13.03. Samples per second 3433.81\n",
      "Iteration 80000 in 23.36 seconds, loss is 13.01. Samples per second 3424.16\n",
      "Iteration 85000 in 24.91 seconds, loss is 12.97. Samples per second 3412.77\n",
      "Iteration 90000 in 26.44 seconds, loss is 12.95. Samples per second 3404.50\n",
      "Iteration 95000 in 27.92 seconds, loss is 12.92. Samples per second 3403.12\n",
      "Iteration 100000 in 29.41 seconds, loss is 12.90. Samples per second 3400.66\n"
     ]
    }
   ],
   "source": [
    "loss, samples_per_second = do_some_training(URM_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated time with the previous training speed is 23524.87 seconds, or 392.08 minutes\n"
     ]
    }
   ],
   "source": [
    "estimated_seconds = 8e6 * 10 / samples_per_second\n",
    "print(\"Estimated time with the previous training speed is {:.2f} seconds, or {:.2f} minutes\".format(estimated_seconds, estimated_seconds/60))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Still far too time consuming\n",
    "### The compiler is just porting in C all operations that the python interpreter would have to perform, dynamic tiping included. Have a look at the html reports in the Cython_examples folder\n",
    "\n",
    "### Now try to add some types: If you use a variable only as a C object, use primitive tipes\n",
    "\n",
    "* cdef int namevar\n",
    "* cdef double namevar\n",
    "* cdef float namevar\n",
    "* cdef double[:] singledimensionarray\n",
    "* cdef double[:,:] bidimensionalmatrix\n",
    "\n",
    "\n",
    "### We now use types for all main variables\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "import numpy as np\n",
    "import time\n",
    "\n",
    "def do_some_training(URM_train):\n",
    "\n",
    "    URM_train_coo = URM_train.tocoo()\n",
    "    n_items = URM_train.shape[1]\n",
    "\n",
    "    cdef double[:,:] item_item_S = np.zeros((n_items, n_items), dtype = np.float)\n",
    "    cdef double learning_rate = 1e-6\n",
    "    cdef double loss = 0.0\n",
    "    cdef long start_time = time.time()\n",
    "    cdef double true_rating, predicted_rating, prediction_error, profile_rating\n",
    "    cdef int[:] items_in_user_profile\n",
    "    cdef double[:] ratings_in_user_profile\n",
    "    cdef int index, sample_num, user_id, item_id, profile_item_id\n",
    "\n",
    "    for sample_num in range(100000):\n",
    "\n",
    "        # Randomly pick sample\n",
    "        sample_index = np.random.randint(URM_train_coo.nnz)\n",
    "\n",
    "        user_id = URM_train_coo.row[sample_index]\n",
    "        item_id = URM_train_coo.col[sample_index]\n",
    "        true_rating = URM_train_coo.data[sample_index]\n",
    "\n",
    "        # Compute prediction\n",
    "        items_in_user_profile = URM_train.indices[URM_train.indptr[user_id]:URM_train.indptr[user_id+1]]\n",
    "        ratings_in_user_profile = URM_train.data[URM_train.indptr[user_id]:URM_train.indptr[user_id+1]]\n",
    "        predicted_rating = 0.0\n",
    "\n",
    "        for index in range(len(items_in_user_profile)):\n",
    "            profile_item_id = items_in_user_profile[index]\n",
    "            profile_rating = ratings_in_user_profile[index]\n",
    "            predicted_rating += profile_rating * item_item_S[profile_item_id,item_id]\n",
    "\n",
    "        # Compute prediction error, or gradient\n",
    "        prediction_error = true_rating - predicted_rating\n",
    "        loss += prediction_error**2\n",
    "\n",
    "        # Update model, in this case the similarity\n",
    "        for index in range(len(items_in_user_profile)):\n",
    "            profile_item_id = items_in_user_profile[index]\n",
    "            profile_rating = ratings_in_user_profile[index]\n",
    "            item_item_S[profile_item_id,item_id] += learning_rate * prediction_error * profile_rating\n",
    "\n",
    "        # Print some stats\n",
    "        if (sample_num +1)% 5000 == 0:\n",
    "            elapsed_time = time.time() - start_time\n",
    "            samples_per_second = (sample_num +1)/elapsed_time\n",
    "            print(\"Iteration {} in {:.2f} seconds, loss is {:.2f}. Samples per second {:.2f}\".format(sample_num+1, elapsed_time, loss/(sample_num +1), samples_per_second))\n",
    "\n",
    "    return loss, samples_per_second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 5000 in 0.58 seconds, loss is 13.30. Samples per second 8652.57\n",
      "Iteration 10000 in 0.70 seconds, loss is 13.31. Samples per second 14301.68\n",
      "Iteration 15000 in 0.80 seconds, loss is 13.30. Samples per second 18743.53\n",
      "Iteration 20000 in 0.90 seconds, loss is 13.33. Samples per second 22275.84\n",
      "Iteration 25000 in 0.98 seconds, loss is 13.27. Samples per second 25484.44\n",
      "Iteration 30000 in 1.08 seconds, loss is 13.26. Samples per second 27745.73\n",
      "Iteration 35000 in 1.17 seconds, loss is 13.25. Samples per second 30019.75\n",
      "Iteration 40000 in 1.27 seconds, loss is 13.22. Samples per second 31590.23\n",
      "Iteration 45000 in 1.35 seconds, loss is 13.19. Samples per second 33311.26\n",
      "Iteration 50000 in 1.44 seconds, loss is 13.18. Samples per second 34829.57\n",
      "Iteration 55000 in 1.54 seconds, loss is 13.14. Samples per second 35810.92\n",
      "Iteration 60000 in 1.62 seconds, loss is 13.12. Samples per second 37025.84\n",
      "Iteration 65000 in 1.72 seconds, loss is 13.08. Samples per second 37773.94\n",
      "Iteration 70000 in 1.80 seconds, loss is 13.06. Samples per second 38912.66\n",
      "Iteration 75000 in 1.88 seconds, loss is 13.04. Samples per second 39819.14\n",
      "Iteration 80000 in 1.97 seconds, loss is 13.01. Samples per second 40647.33\n",
      "Iteration 85000 in 2.07 seconds, loss is 12.99. Samples per second 41094.20\n",
      "Iteration 90000 in 2.15 seconds, loss is 12.96. Samples per second 41801.01\n",
      "Iteration 95000 in 2.24 seconds, loss is 12.94. Samples per second 42453.96\n",
      "Iteration 100000 in 2.32 seconds, loss is 12.92. Samples per second 43059.92\n"
     ]
    }
   ],
   "source": [
    "loss, samples_per_second = do_some_training(URM_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated time with the previous training speed is 1857.88 seconds, or 30.96 minutes\n"
     ]
    }
   ],
   "source": [
    "estimated_seconds = 8e6 * 10 / samples_per_second\n",
    "print(\"Estimated time with the previous training speed is {:.2f} seconds, or {:.2f} minutes\".format(estimated_seconds, estimated_seconds/60))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### This is why we use it for machine learning algorithms...\n",
    "\n",
    "### Some operations are still done with sparse matrices, those cannot be correctly optimized because the compiler does not know how what is the type of the data.\n",
    "\n",
    "### To address this, we create typed arrays in which we put the URM_train data\n",
    "####  For example, this operation: user_id = URM_train_coo.row[sample_index]\n",
    "#### Becomes:\n",
    "#### cdef int user_id\n",
    "#### cdef int[:] URM_train_coo_row = URM_train_coo.row\n",
    "#### user_id = URM_train_coo_row[sample_index]\n",
    "\n",
    "### We can also skip the creation of the items_in_user_profile array and replace the np.random call with the faster native C function rand()\n",
    "\n",
    "## To obtain a more reliable speed estimate we increase the number of samples and the print step by a factor of 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "\n",
    "import numpy as np\n",
    "import time\n",
    "\n",
    "from libc.stdlib cimport rand, srand, RAND_MAX\n",
    "\n",
    "def do_some_training(URM_train):\n",
    "\n",
    "    URM_train_coo = URM_train.tocoo()\n",
    "    cdef int n_items = URM_train.shape[1]\n",
    "    cdef int n_interactions = URM_train.nnz\n",
    "    cdef int[:] URM_train_coo_row = URM_train_coo.row\n",
    "    cdef int[:] URM_train_coo_col = URM_train_coo.col\n",
    "    cdef double[:] URM_train_coo_data = URM_train_coo.data\n",
    "    cdef int[:] URM_train_indices = URM_train.indices\n",
    "    cdef int[:] URM_train_indptr = URM_train.indptr\n",
    "    cdef double[:] URM_train_data = URM_train.data\n",
    "\n",
    "    cdef double[:,:] item_item_S = np.zeros((n_items, n_items), dtype = np.float)\n",
    "    cdef double learning_rate = 1e-6\n",
    "    cdef double loss = 0.0\n",
    "    cdef long start_time = time.time()\n",
    "    cdef double true_rating, predicted_rating, prediction_error, profile_rating\n",
    "    cdef int start_profile, end_profile\n",
    "    cdef int index, sample_num, user_id, item_id, profile_item_id\n",
    "\n",
    "    for sample_num in range(1000000):\n",
    "\n",
    "        # Randomly pick sample\n",
    "        index = rand() % n_interactions\n",
    "\n",
    "        user_id = URM_train_coo_row[index]\n",
    "        item_id = URM_train_coo_col[index]\n",
    "        true_rating = URM_train_coo_data[index]\n",
    "\n",
    "        # Compute prediction\n",
    "        start_profile = URM_train_indptr[user_id]\n",
    "        end_profile = URM_train_indptr[user_id+1]\n",
    "        predicted_rating = 0.0\n",
    "\n",
    "        for index in range(start_profile, end_profile):\n",
    "            profile_item_id = URM_train_indices[index]\n",
    "            profile_rating = URM_train_data[index]\n",
    "            predicted_rating += item_item_S[profile_item_id,item_id] * profile_rating\n",
    "\n",
    "        # Compute prediction error, or gradient\n",
    "        prediction_error = true_rating - predicted_rating\n",
    "        loss += prediction_error**2\n",
    "\n",
    "        # Update model, in this case the similarity\n",
    "        for index in range(start_profile, end_profile):\n",
    "            profile_item_id = URM_train_indices[index]\n",
    "            profile_rating = URM_train_data[index]\n",
    "            item_item_S[profile_item_id,item_id] += learning_rate * prediction_error * profile_rating\n",
    "\n",
    "        # Print some stats\n",
    "        if (sample_num +1)% 50000 == 0:\n",
    "            elapsed_time = time.time() - start_time\n",
    "            samples_per_second = (sample_num +1)/elapsed_time\n",
    "            print(\"Iteration {} in {:.2f} seconds, loss is {:.2f}. Samples per second {:.2f}\".format(sample_num+1, elapsed_time, loss/(sample_num +1), samples_per_second))\n",
    "\n",
    "    return loss, samples_per_second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 50000 in 1.08 seconds, loss is 13.55. Samples per second 46332.34\n",
      "Iteration 100000 in 1.53 seconds, loss is 13.20. Samples per second 65170.61\n",
      "Iteration 150000 in 2.02 seconds, loss is 12.88. Samples per second 74338.63\n",
      "Iteration 200000 in 2.50 seconds, loss is 12.56. Samples per second 79870.62\n",
      "Iteration 250000 in 2.96 seconds, loss is 12.27. Samples per second 84338.99\n",
      "Iteration 300000 in 3.43 seconds, loss is 11.99. Samples per second 87469.95\n",
      "Iteration 350000 in 3.92 seconds, loss is 11.72. Samples per second 89373.33\n",
      "Iteration 400000 in 4.37 seconds, loss is 11.47. Samples per second 91484.56\n",
      "Iteration 450000 in 4.82 seconds, loss is 11.23. Samples per second 93398.33\n",
      "Iteration 500000 in 5.28 seconds, loss is 11.01. Samples per second 94777.66\n",
      "Iteration 550000 in 5.72 seconds, loss is 10.79. Samples per second 96108.86\n",
      "Iteration 600000 in 6.18 seconds, loss is 10.58. Samples per second 97114.74\n",
      "Iteration 650000 in 6.62 seconds, loss is 10.39. Samples per second 98219.46\n",
      "Iteration 700000 in 7.08 seconds, loss is 10.20. Samples per second 98811.27\n",
      "Iteration 750000 in 7.55 seconds, loss is 10.03. Samples per second 99370.70\n",
      "Iteration 800000 in 8.00 seconds, loss is 9.86. Samples per second 99950.33\n",
      "Iteration 850000 in 8.47 seconds, loss is 9.69. Samples per second 100334.45\n",
      "Iteration 900000 in 8.94 seconds, loss is 9.54. Samples per second 100708.21\n",
      "Iteration 950000 in 9.41 seconds, loss is 9.39. Samples per second 100959.40\n",
      "Iteration 1000000 in 9.89 seconds, loss is 9.25. Samples per second 101149.65\n"
     ]
    }
   ],
   "source": [
    "loss, samples_per_second = do_some_training(URM_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated time with the previous training speed is 790.91 seconds, or 13.18 minutes\n"
     ]
    }
   ],
   "source": [
    "estimated_seconds = 8e6 * 10 / samples_per_second\n",
    "print(\"Estimated time with the previous training speed is {:.2f} seconds, or {:.2f} minutes\".format(estimated_seconds, estimated_seconds/60))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### As the source code gets less readable due to the addition of types and native C functions, it also gets remarkably faster\n",
    "\n",
    "### We started from a naive python implementation which took 10 hours (2k samples per second) and we now have a Cython one with takes 12 minutes (100k samples per second)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "\n",
    "import numpy as np\n",
    "import time\n",
    "\n",
    "from libc.stdlib cimport rand, srand, RAND_MAX\n",
    "\n",
    "def train_multiple_epochs(URM_train, learning_rate_input, n_epochs):\n",
    "\n",
    "    URM_train_coo = URM_train.tocoo()\n",
    "    cdef int n_items = URM_train.shape[1]\n",
    "    cdef int n_interactions = URM_train.nnz\n",
    "    cdef int[:] URM_train_coo_row = URM_train_coo.row\n",
    "    cdef int[:] URM_train_coo_col = URM_train_coo.col\n",
    "    cdef double[:] URM_train_coo_data = URM_train_coo.data\n",
    "    cdef int[:] URM_train_indices = URM_train.indices\n",
    "    cdef int[:] URM_train_indptr = URM_train.indptr\n",
    "    cdef double[:] URM_train_data = URM_train.data\n",
    "\n",
    "    cdef double[:,:] item_item_S = np.zeros((n_items, n_items), dtype = np.float)\n",
    "    cdef double learning_rate = learning_rate_input\n",
    "    cdef double loss = 0.0\n",
    "    cdef long start_time\n",
    "    cdef double true_rating, predicted_rating, prediction_error, profile_rating\n",
    "    cdef int start_profile, end_profile\n",
    "    cdef int index, sample_num, user_id, item_id, profile_item_id\n",
    "    \n",
    "    for n_epoch in range(n_epochs):\n",
    "        \n",
    "        loss = 0.0\n",
    "        start_time = time.time()\n",
    "        \n",
    "        for sample_num in range(n_interactions):\n",
    "\n",
    "            # Randomly pick sample\n",
    "            index = rand() % n_interactions\n",
    "\n",
    "            user_id = URM_train_coo_row[index]\n",
    "            item_id = URM_train_coo_col[index]\n",
    "            true_rating = URM_train_coo_data[index]\n",
    "\n",
    "            # Compute prediction\n",
    "            start_profile = URM_train_indptr[user_id]\n",
    "            end_profile = URM_train_indptr[user_id+1]\n",
    "            predicted_rating = 0.0\n",
    "\n",
    "            for index in range(start_profile, end_profile):\n",
    "                profile_item_id = URM_train_indices[index]\n",
    "                profile_rating = URM_train_data[index]\n",
    "                predicted_rating += item_item_S[profile_item_id,item_id] * profile_rating\n",
    "\n",
    "            # Compute prediction error, or gradient\n",
    "            prediction_error = true_rating - predicted_rating\n",
    "            loss += prediction_error**2\n",
    "\n",
    "            # Update model, in this case the similarity\n",
    "            for index in range(start_profile, end_profile):\n",
    "                profile_item_id = URM_train_indices[index]\n",
    "                profile_rating = URM_train_data[index]\n",
    "                item_item_S[profile_item_id,item_id] += learning_rate * prediction_error * profile_rating\n",
    "\n",
    "#             # Print some stats\n",
    "#             if (sample_num +1)% 1000000 == 0:\n",
    "#                 elapsed_time = time.time() - start_time\n",
    "#                 samples_per_second = (sample_num+1)/elapsed_time\n",
    "#                 print(\"Iteration {} in {:.2f} seconds, loss is {:.2f}. Samples per second {:.2f}\".format(sample_num+1, elapsed_time, loss/(sample_num+1), samples_per_second))\n",
    "\n",
    "            \n",
    "        elapsed_time = time.time() - start_time\n",
    "        samples_per_second = (sample_num+1)/elapsed_time\n",
    "     \n",
    "        print(\"Epoch {} complete in in {:.2f} seconds, loss is {:.3E}. Samples per second {:.2f}\".format(n_epoch+1, time.time() - start_time, loss/(sample_num+1), samples_per_second))\n",
    "\n",
    "    return np.array(item_item_S), loss/(sample_num+1), samples_per_second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 1 complete in in 74.06 seconds, loss is 9.571E-02. Samples per second 108034.40\n",
      "Epoch 2 complete in in 72.56 seconds, loss is 6.914E-05. Samples per second 110261.76\n",
      "Epoch 3 complete in in 73.60 seconds, loss is 8.308E-06. Samples per second 108705.13\n",
      "Epoch 4 complete in in 72.17 seconds, loss is 1.526E-06. Samples per second 110856.24\n",
      "Epoch 5 complete in in 73.03 seconds, loss is 3.504E-07. Samples per second 109560.72\n",
      "Epoch 6 complete in in 72.54 seconds, loss is 8.842E-08. Samples per second 110298.41\n",
      "Epoch 7 complete in in 74.30 seconds, loss is 2.332E-08. Samples per second 107681.97\n",
      "Epoch 8 complete in in 72.96 seconds, loss is 6.066E-09. Samples per second 109665.92\n",
      "Epoch 9 complete in in 75.92 seconds, loss is 1.717E-09. Samples per second 105388.01\n",
      "Epoch 10 complete in in 74.96 seconds, loss is 4.639E-10. Samples per second 106735.14\n"
     ]
    }
   ],
   "source": [
    "n_items = URM_train.shape[1]\n",
    "learning_rate = 1e-4\n",
    "    \n",
    "item_item_S, loss, samples_per_second = train_multiple_epochs(URM_train, learning_rate, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.07723263, 0.04613929, 0.06089555, ..., 0.        , 0.        ,\n",
       "        0.        ],\n",
       "       [0.05279096, 0.24018039, 0.00607983, ..., 0.        , 0.        ,\n",
       "        0.        ],\n",
       "       [0.05279096, 0.07732453, 0.31195645, ..., 0.        , 0.        ,\n",
       "        0.        ],\n",
       "       ...,\n",
       "       [0.        , 0.        , 0.        , ..., 0.        , 0.        ,\n",
       "        0.        ],\n",
       "       [0.        , 0.        , 0.        , ..., 0.        , 0.        ,\n",
       "        0.        ],\n",
       "       [0.        , 0.        , 0.        , ..., 0.        , 0.        ,\n",
       "        0.        ]])"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "item_item_S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Note how the loss decreased?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## How to use Cython outside a notebook\n",
    "\n",
    "### Step1: Create a .pyx file and write your code\n",
    "\n",
    "### Step2: Create a compilation script \"compileCython.py\" with the following content"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "# This code will not run in a notebook cell\n",
    "\n",
    "try:\n",
    "    from setuptools import setup\n",
    "    from setuptools import Extension\n",
    "except ImportError:\n",
    "    from distutils.core import setup\n",
    "    from distutils.extension import Extension\n",
    "\n",
    "\n",
    "from Cython.Distutils import build_ext\n",
    "import numpy\n",
    "import sys\n",
    "import re\n",
    "\n",
    "\n",
    "if len(sys.argv) != 4:\n",
    "    raise ValueError(\"Wrong number of paramethers received. Expected 4, got {}\".format(sys.argv))\n",
    "\n",
    "\n",
    "# Get the name of the file to compile\n",
    "fileToCompile = sys.argv[1]\n",
    "\n",
    "# Remove the argument from sys argv in order for it to contain only what setup needs\n",
    "del sys.argv[1]\n",
    "\n",
    "extensionName = re.sub(\"\\.pyx\", \"\", fileToCompile)\n",
    "\n",
    "\n",
    "ext_modules = Extension(extensionName,\n",
    "                [fileToCompile],\n",
    "                extra_compile_args=['-O3'],\n",
    "                include_dirs=[numpy.get_include(),],\n",
    "                )\n",
    "\n",
    "setup(\n",
    "    cmdclass={'build_ext': build_ext},\n",
    "    ext_modules=[ext_modules]\n",
    ")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step3: Compile your code with the following command \n",
    "\n",
    "python compileCython.py Cython_examples\\SLIM_MSE_fastest.pyx build_ext --inplace"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step4: Generate cython report and look for \"yellow lines\". The report is an .html file which represents how many operations are necessary to translate each python operation in cython code. If a line is white, it has a direct C translation. If it is yellow it will require many indirect steps that will slow down execution. Some of those steps may be inevitable, some may be removed via static typing.\n",
    "\n",
    "### IMPORTANT: white does not mean fast!! If a system call is involved that part might be slow anyway.\n",
    "\n",
    "cython -a Cython_examples\\SLIM_MSE_fastest.pyx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step5: Add static types and C functions to remove \"yellow\" lines.\n",
    "\n",
    "#### If you use a variable only as a C object, use primitive tipes \n",
    "cdef int namevar\n",
    "\n",
    "def double namevar\n",
    "\n",
    "cdef float namevar\n",
    "\n",
    "#### If you call a function only within C code, use a specific declaration \"cdef\"\n",
    "\n",
    "cdef function_name(self, int param1, double param2):\n",
    "...\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step6: Iterate step 4 and 5 until you are satisfied with how clean your code is, then compile. An example of non optimized code can be found in the source folder of this notebook with the _SLOW suffix\n",
    "\n",
    "## Step7: the compilation generates a file wose name is something like \"SLIM_MSE_fastest.cp36-win_amd64.pyd\" and tells you the source file, the architecture it is compiled for and the OS\n",
    "\n",
    "## Step8: Import and use the compiled file as if it were any python object, function or class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Cython_examples.SLIM_MSE_fastest import train_multiple_epochs\n",
    "\n",
    "train_multiple_epochs(URM_train, 1e-3, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A few warnings on ML algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### - Why do we bother with KNNs if we have ML?\n",
    "#### Because sometimes ML algorithms work better than heuristic ones, sometimes they do not\n",
    "\n",
    "### - ML algorithms are always best because they learn from the data\n",
    "#### Not really... Yes they learn from the data but the data is sometimes too noisy, too sparse and does not yeld good results. There is plenty of examples of cases where ML algorithms are not the best choice.\n",
    "\n",
    "### - We should use this complex model because it can in theory approximate any function!!\n",
    "#### Theory is important but... does it work in practice? Often complex modes are veeeery difficult to train and you need to use lots of tricks: adaptive gradients, data normalization, careful initialization and crafted batches...\n",
    "\n",
    "### - I have trained my model for 2 epochs but the result is not great\n",
    "#### Have you just used the default learning rate or have you optimized it? Why did you stop after 2 epochs? You may need 100s of epochs\n",
    "\n",
    "### - If I select a high learning rate (maybe 1e-3) after 5 epochs I get a result wich is not very good, if I use a lower learning rate (maybe 1e-6) the result is much worse\n",
    "#### Of course, the lower the learning rate the slower the training process but the best solution you may find. Again, you may need 100s of epochs\n",
    "\n",
    "### - Training and optimizing the hyperparameters of this ML model takes several hours, what am I doing wrong?\n",
    "#### Probably nothing, ML is computationally expensive and takes time... A few hours is a normal timespan. Sometimes the end result is still not satisfactory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
